
#include "alloc_list.h"
#include "alloc_context_impl.h"
#include "alloc.h"

static List *
alloc_list_from_chunk( ListChunk * chunk )
{
    size_t  i;
    int     mask = 1;

    assert( chunk->free_mask != UINT_MAX );
    
    for( i = 0; i < QL_CHUNK_NUM_BITS; ++ i )
    {
        if( 0 == (chunk->free_mask & mask) )
        {
            // mark place as busy
            chunk->free_mask |= mask;
            return &chunk->arr[i];
        }

        mask = mask << 1;
    }

    assert( !"should never come here" );
    return 0;
}

static List *
find_free_element_from_blocks( AllocContext * c )
{
    ListBlock * b;
    for( b = c->impl->lists.blk; b != 0; b = b->next )
    {
        size_t      i;
        
        for( i = b->nfc_index; i < c->settings.list_chunks_alloc_size; ++ i )
        {
            ListChunk *  chunk = &b->chunks[i];
            if( chunk->free_mask != UINT_MAX )
            {
                // free chunk has been found!
                List * result = alloc_list_from_chunk( chunk );
                
                // update `last free chunk index' for this block if
                // it pointed for this block before
                if( chunk->free_mask == UINT_MAX && b->nfc_index == i )
                {
                    b->nfc_index = i + 1;
                }

                return result;
            }
        }
    }

    return 0;
}

static List * alloc_empty_list( AllocContext * c )
{
    List *          result;
    ListBlock *     b;

    result = find_free_element_from_blocks( c );
    if( !result )
    {
        // need to allocate one another block (all the blocks busy)
        ListBlock * new_block = ql_mallocz( c,
            sizeof(ListChunk) * (c->settings.list_chunks_alloc_size - 1) + sizeof(ListBlock) );

        b = c->impl->lists.blk;
        new_block->next = b;
        c->impl->lists.blk = new_block;

        // since new block is allocated - the following function must succeed
        result = find_free_element_from_blocks( c );
        assert( result != 0 );
    }

    return result;
}

List * alloc_list( AllocContext * c )
{
    List *  result = alloc_empty_list( c );
    
    result->type = OBJ_LIST;
    result->car = 0;
    result->cdr = 0;

    return result;
}

/*
 * removes just one list and does not care about its contents
 */
static void free_one_list( AllocContext * c, List * list )
{
    ListBlock *     b;

    const void *    p = list;
    ListChunk *     chunk;
    size_t          chunk_index;
    size_t          arr_index;

    // find block the given list belongs to
    for( b = c->impl->lists.blk; b != 0; b = b->next )
    {
        void * left = b;
        void * right = (char *)b + sizeof(ListBlock) + (c->settings.list_chunks_alloc_size - 1) * sizeof(ListChunk);
        if( (p > left) && (p < right) )
        {
            break;
        }
    }

    // block may not be null and list address shall not be less than the first one chunk entry
    if( (0 == b) || (p < (const void *)&b->chunks[0].arr[0]) )
    {
        assert( !"given pointer does not belong to this context" );
        alloc_emit_error( c, QL_ERR_WRONG_LIST_TO_FREE );
    }

    // get chunk index
    chunk_index = (((size_t)p) - ((size_t)b->chunks)) / sizeof(ListChunk);
    if( chunk_index >= QL_ERR_WRONG_LIST_TO_FREE )
    {
        assert( !"chunk index too big - this should never happen" );
        alloc_emit_error( c, QL_ERR_WRONG_LIST_TO_FREE );
    }

    chunk = &b->chunks[chunk_index];

    // now find offset in chunk arr
    arr_index = (size_t)p - (size_t)chunk->arr;
    if( 0 != (arr_index % sizeof(List)) )
    {
        assert( !"non-existent index in chunk found - this should never happen" );
        alloc_emit_error( c, QL_ERR_WRONG_LIST_TO_FREE );
    }

    // calculate an exact index
    arr_index = arr_index / sizeof(List);
    if( arr_index > QL_CHUNK_NUM_BITS )
    {
        assert( !"too big index in the chunk array - this should never happen" );
        alloc_emit_error( c, QL_ERR_WRONG_LIST_TO_FREE );
    }

    // so at last index found - re-check that
    assert( chunk->arr + arr_index == list );

    // mark this list as free
    chunk->free_mask &= ~(1 << arr_index);

    // update last free chunk index if it is needed
    if( b->nfc_index > chunk_index )
    {
        b->nfc_index = chunk_index;
    }

    // uninitialize this element by filling its contents with zeroes
    list->car = 0;
    list->cdr = 0;
    list->type = OBJ_UNDEFINED;
}

void free_list( AllocContext * c, List * list )
{
    // does not walks through the list - just removes one another chain
    free_one_list( c, list );

}

void free_lists_buffers( AllocContext * c )
{
    ListBlock * b = c->impl->lists.blk;

    // free each block
    for( ; b != 0; )
    {
        ListBlock *  next_block = b->next;
        ql_free( b );
        b = next_block;
    }
}
